package 跳表;

import java.util.Random;

// 跳表节点
class Node {
    int value;
    Node[] forward;  // 向前指针数组

    public Node(int value, int level) {
        this.value = value;
        this.forward = new Node[level + 1]; // 创建指定层数的指针数组
    }
}

// 跳表
public class SkipList {
    private static final int MAX_LEVEL = 16;  // 最大层数
    private Node header;  // 跳表头节点
    private int level;  // 当前跳表的层数
    private Random random;

    public SkipList() {
        this.level = 0;
        this.header = new Node(-1, MAX_LEVEL); // 创建一个虚拟的头节点
        this.random = new Random();
    }

    // 创建一个随机层数
    private int randomLevel() {
        int newLevel = 0;
        while (random.nextInt(2) == 1 && newLevel < MAX_LEVEL) {
            newLevel++;
        }
        return newLevel;
    }

    // 插入一个值
    public void insert(int value) {
        Node[] update = new Node[MAX_LEVEL + 1];  // 保存每一层需要更新的节点
        Node current = header;

        // 从跳表的最大层开始向下查找
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && current.forward[i].value < value) {
                current = current.forward[i];
            }
            update[i] = current;  // 记录每一层的前一个节点
        }

        // 创建新的节点
        int newLevel = randomLevel();
        if (newLevel > level) {
            for (int i = level + 1; i <= newLevel; i++) {
                update[i] = header;  // 更新每一层的指针
            }
            level = newLevel;  // 更新当前跳表的层数
        }

        Node newNode = new Node(value, newLevel);
        for (int i = 0; i <= newLevel; i++) {
            newNode.forward[i] = update[i].forward[i];  // 将新节点的forward指向正确的节点
            update[i].forward[i] = newNode;  // 更新前一个节点的指针
        }
    }

    // 删除一个值
    public void delete(int value) {
        Node[] update = new Node[MAX_LEVEL + 1];
        Node current = header;

        // 从跳表的最大层开始向下查找
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && current.forward[i].value < value) {
                current = current.forward[i];
            }
            update[i] = current;  // 记录每一层的前一个节点
        }

        // 查找是否找到了要删除的节点
        current = current.forward[0];
        if (current != null && current.value == value) {
            // 删除每一层中的节点
            for (int i = 0; i <= level; i++) {
                if (update[i].forward[i] != current) break;
                update[i].forward[i] = current.forward[i];
            }

            // 更新跳表的层数
            while (level > 0 && header.forward[level] == null) {
                level--;
            }
        }
    }

    // 查找一个值
    public boolean search(int value) {
        Node current = header;
        // 从跳表的最大层开始向下查找
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && current.forward[i].value < value) {
                current = current.forward[i];
            }
        }
        current = current.forward[0];
        return current != null && current.value == value;
    }

    // 打印跳表
    public void printList() {
        System.out.println("SkipList:");
        for (int i = level; i >= 0; i--) {
            Node current = header.forward[i];
            System.out.print("Level " + i + ": ");
            while (current != null) {
                System.out.print(current.value + " ");
                current = current.forward[i];
            }
            System.out.println();
        }
    }

    // 测试跳表的CRUD操作
    public static void main(String[] args) {
        SkipList skipList = new SkipList();

        // 插入操作
        skipList.insert(10);
        skipList.insert(20);
        skipList.insert(30);
        skipList.insert(50);
        skipList.insert(40);
        skipList.insert(70);
        skipList.insert(60);
        skipList.printList();

        // 查找操作
        System.out.println("Search 20: " + skipList.search(20));  // true
        System.out.println("Search 100: " + skipList.search(100));  // false

        // 删除操作
        skipList.delete(30);
        skipList.printList();
    }
}
